package main

import "fmt"

func main() {
	beginWord := "hit"
	endWord := "cog"
	wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
	beginWord = "hot"
	endWord = "dog"
	wordList = []string{"hot", "dot", "dog"}
	beginWord = "a"
	endWord = "c"
	wordList = []string{"a", "b", "c"}
	len := ladderLength(beginWord, endWord, wordList)
	fmt.Println(len)

}

func findNextWordList(word string, wordList []string, wordMap map[string]int) []string {
	nextWordLst := make([]string, 0)
	wordLen := len(word)

	for i := 0; i < len(wordList); i++ {
		if wordMap[wordList[i]] == 1 {
			continue
		}
		sameLetterNum := 0
		for j := 0; j < wordLen; j++ {
			if word[j] == wordList[i][j] {
				sameLetterNum++
			}
		}
		if sameLetterNum+1 == wordLen {
			wordMap[wordList[i]] = 1
			nextWordLst = append(nextWordLst, wordList[i])
		}
	}
	return nextWordLst
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
	wordMap := make(map[string]int)
	for i := 0; i < len(wordList); i++ {
		wordMap[wordList[i]] = 0
	}
	if _, ok := wordMap[endWord]; !ok {
		return 0
	}
	curWordLst := make([]string, 0)
	curWordLst = append(curWordLst, beginWord)
	level := 0
	find := false
	for {
		level++
		if len(curWordLst) == 0 {
			break
		}
		nextWordLst := make([]string, 0)
		for _, word := range curWordLst {
			if word == endWord {
				find = true
				break
			}
			anextWordLst := findNextWordList(word, wordList, wordMap)
			if len(anextWordLst) != 0 {
				nextWordLst = append(nextWordLst, anextWordLst...)
			}
		}
		if find {
			break
		}
		curWordLst = curWordLst[0:0]
		if len(nextWordLst) > 0 {
			curWordLst = make([]string, len(nextWordLst))
			copy(curWordLst, nextWordLst)
			nextWordLst = nextWordLst[0:0]
		}
	}
	if !find {
		level = 0
	}

	return level
}
